/*
day255
2020.5.9
*/
#include<stack>
#include<vector>
#include<cstdlib> 
using namespace std;

struct TreeNode {
    int val;
	TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
    	vector<vector<int>> res;
    	int state=1; 
    	if(!root)
    	{
    		return res;
		}
		
		stack<TreeNode*> *sta_A=new stack<TreeNode*>();
		stack<TreeNode*> *sta_B=new stack<TreeNode*>();
		(*sta_A).push(root);
		
		while(!(*sta_A).empty())
		{
			vector<int> vec_tem;
			int size=(*sta_A).size();
			for(int i=0;i<size;++i)
			{
				TreeNode *tem=(*sta_A).top();
				(*sta_A).pop();
				vec_tem.push_back(tem->val);
				
				
				if(state==1)
				{
					if(tem->left)
					{
						(*sta_B).push(tem->left);
					}
					
					if(tem->right)
					{
						(*sta_B).push(tem->right);
					}
				 } 
			
				else 
				{
					if(tem->right)
					{
						(*sta_B).push(tem->right);
					}
					
					if(tem->left)
					{
						(*sta_B).push(tem->left);
					}
				}
				
			}
			res.push_back(vec_tem);
			
			stack<TreeNode*> *t=sta_A;
			sta_A=sta_B;
			sta_B=t;
			state=-1*state;
		}
		
		return res;
    }
};


int main()
{
	return 0;
}

